package com.shuang.tree45;

public class SortedArrayToBST {

//    public TreeNode sortedArrayToBST(int[] nums) {
//        TreeNode root = traversal(nums, 0, nums.length - 1);
//        return root;
//    }
//
//    // 左闭右闭区间[left, right]
//    private TreeNode traversal(int[] nums, int left, int right) {
//
//        if (left > right)
//            return null;
//
//        int mid = left + ((right - left) >> 1);
//
//        TreeNode root = new TreeNode(nums[mid]);
//
//        root.left = traversal(nums, left, mid - 1);
//        root.right = traversal(nums, mid + 1, right);
//
//        return root;
//    }

    public TreeNode sortedArrayToBST(int[] nums) {
        return sortedArrayToBST(nums, 0, nums.length);
    }

    //左闭右开
    public TreeNode sortedArrayToBST(int[] nums, int left, int right) {
        //终止条件
        if (left >= right) {
            return null;
        }

        //区间只有一个元素符合的时候
        if (right - left == 1) {
            return new TreeNode(nums[left]);
        }

        //取区间中间索引 防止溢出
        int mid = left + (right - left) / 2;

        TreeNode root = new TreeNode(nums[mid]);

        root.left = sortedArrayToBST(nums, left, mid);
        root.right = sortedArrayToBST(nums, mid + 1, right);

        return root;
    }
}
